package com.lw.leetcode.sort.c;

import java.util.Arrays;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 2382. 删除操作后的最大子段和
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/22 15:08
 */
public class MaximumSegmentSum {

    public static void main(String[] args) {
        MaximumSegmentSum test = new MaximumSegmentSum();

        // [14,7,2,2,0]
//        int[] arr = {1, 2, 5, 6, 1};
//        int[] res = {0, 3, 2, 4, 1};

        // [16,5,3,0]
        int[] arr = {3, 2, 11, 1};
        int[] res = {3, 2, 1, 0};

        long[] longs = test.maximumSegmentSum(arr, res);
        long a = 1000000000L * 100000;

        System.out.println(a << 17);
        System.out.println((a << 17) >>> 17);
        System.out.println(Arrays.toString(longs));
    }

    public long[] maximumSegmentSum(int[] nums, int[] removeQueries) {
        int length = nums.length;
        long[] sums = new long[length + 1];
        for (int i = 0; i < length; i++) {
            sums[i + 1] = sums[i] + nums[i];
        }
        TreeMap<Integer, Integer> map = new TreeMap<>();
        PriorityQueue<Long> queue = new PriorityQueue<>((a, b) -> Long.compare(b >>> 17, a >>> 17));
        map.put(0, length - 1);
        queue.add(sums[length] << 17);
        int l = removeQueries.length;
        long[] values = new long[l];
        for (int i = 0; i < l; i++) {
            int index = removeQueries[i];
            Map.Entry<Integer, Integer> entry = map.floorEntry(index);
            int key = entry.getKey();
            int value = entry.getValue();
            if (index == key) {
                map.remove(key);
                if (value != key) {
                    map.put(key + 1, value);
                    queue.add(((sums[value + 1] - sums[key + 1]) << 17) + key + 1);
                }
            } else if (index == value) {
                map.put(key, value - 1);
                queue.add(((sums[value] - sums[key]) << 17) + key);
            } else {
                map.put(key, index - 1);
                queue.add(((sums[index] - sums[key]) << 17) + key);
                map.put(index + 1, value);
                queue.add(((sums[value + 1] - sums[index + 1]) << 17) + index + 1);
            }
            while (!queue.isEmpty()) {
                long poll = queue.peek();
                long s = poll >>> 17;
                int st = (int) (poll & 0X1FFFF);
                Integer v = map.get(st);
                if (v != null && sums[v + 1] - sums[st] == s) {
                    values[i] = s;
                    break;
                } else {
                    queue.poll();
                }
            }
        }
        return values;
    }

}
